﻿// 0908train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 给定一个二维的m×n网格地图（grids二维数组），每个单元格0为空，1是障碍物，2是红绿灯；
 每一步可以在0或者2的单元格移动，每一秒可以走一个单元格；
 遇到红绿灯想要通过需要等待不同的时间才能通过，大小为lights数组标注灯的坐标和等待时间，例如(2,2,3)，
 坐标(2,2)红绿灯等待时间3秒，问从左上角(0,0)到右下角(m-1,n-1)所需的最短时间。

输入描述：
第一行输入grids二维数组，内部数据只有0，1，2，1<m,n<=100  
第二行输入lights红绿灯二维数组，1<x<=m×n  

输出描述：
从坐标(0,0)到(m-1,n-1)坐标所需的最短时间，如果没有路径，则返回最短时间为-1。

示例1  
输入  
[[0,1,0],[0,2,1],[0,0,0]]  
[[1,1,3]]  
输出  
4
[
[0,1,0],
[0,2,1],
[0,0,0]]
 */
class Solution01
{
public:
    void initMap(vector<int>&wait_item_v)
    {
        string key;
        key += to_string(wait_item_v[0]);
        key += ',';
        key += to_string(wait_item_v[1]);

        wait_map[key] = wait_item_v[2];
        //initMap
    }

    int getCurrCost(int r, int c)
    {
        string key;
        key += to_string(r);
        key += ',';
        key += to_string(c);

        if (wait_map.count(key)>0)
        {
            //加上等待时间
            return wait_map.at(key) + 1;
        }

        return 1;
        //getMapKey
    }

    bool checkAvailable(vector<vector<int>>& grid, int r,int c)
    {
        return grid[r][c] == 0 || grid[r][c] == 2;
    }

    void backTrack(vector<vector<int>>& grid, vector<vector<bool>>&checked, int prev_r, int prev_c)
    {
        for (auto&dir_vec:DirectionGrid)
        {
            //不越界，未访问，满足条件
            int curr_r = prev_r + dir_vec[0];
            int curr_c = prev_c + dir_vec[1];

            if (curr_r == row_size-1 && curr_c == col_size-1)
            {
                //判断终点是否能访问
                //加上终点花费时间
                bool is_available = checkAvailable(grid, curr_r, curr_c);
                if (is_available)
                {
                    int total_sum = 0;
                    for (auto&num:curr_cost_v)
                    {
                        total_sum += num;
                    }
                    //加上终点的步数
                    total_sum += getCurrCost(curr_r, curr_c);

                    is_find = true;
                    result_cost = min(total_sum, result_cost);
                    return;
                }
            }

            bool is_curr_r = curr_r >= 0 && curr_r < row_size;
            bool is_curr_c = curr_c >= 0 && curr_c < col_size;

            if (is_curr_r && is_curr_c)
            {
                bool is_visited = checked[curr_r][curr_c];
                bool is_available = checkAvailable(grid, curr_r, curr_c);

                if (!is_visited && is_available)
                {
                    //做选择
                    checked[curr_r][curr_c] = true;
                    curr_cost_v.push_back(getCurrCost(curr_r, curr_c));
                    //回溯
                    backTrack(grid, checked, curr_r, curr_c);
                    //撤销选择
                    checked[curr_r][curr_c] = false;
                    curr_cost_v.pop_back();
                }

            }
	        //dir_vec
        }

        //backTrack
    }

    void solve01(vector<vector<int>>& grid, vector<vector<int>>& wait_vec)
    {
        for (auto& min_vec : wait_vec)
        {
            initMap(min_vec);
        }

        //三件套 checked DirectionGrid bfs_queue
        row_size = grid.size();
        col_size = grid[0].size();

        vector<bool>checked_status(col_size, false);
        vector<vector<bool>>checked(row_size, checked_status);

        checked[0][0] = true;
        //感觉更像是回溯
        backTrack(grid, checked, 0, 0);

        if (is_find)
        {
            cout << result_cost;
            return;
        }
        cout << -1;
    }

    vector<vector<int>>handleStr(string& grid_str)
    {
        grid_str = grid_str.substr(1, grid_str.size() - 2);

        vector<vector<int>>grid;
        vector<int>min_vec;
        int curr_num = 0;
        bool min_vec_start = false;
        for (int i = 0; i < grid_str.size(); i++)
        {
            char curr_char = grid_str[i];
            if (curr_char == '[')
            {
                min_vec_start = true;
            }
            else if (isdigit(curr_char))
            {
                curr_num = curr_num * 10 + grid_str[i] - '0';
            }
            else if (curr_char == ',' && min_vec_start)
            {
                min_vec.push_back(curr_num);
                curr_num = 0;
            }
            else if (curr_char == ']')
            {
                //推进最后一个数
                min_vec.push_back(curr_num);
                curr_num = 0;
                min_vec_start = false;
                grid.push_back(min_vec);
                min_vec.clear();
            }
        }
        return grid;

        //handleStr
    }
    
    Solution01(string&grid_str, string&wait_str)
    {
        vector<vector<int>>grid = handleStr(grid_str);
        vector<vector<int>>wait_vec = handleStr(wait_str);

        solve01(grid, wait_vec);
        //Solution01
    }
private:
    int row_size = 0, col_size = 0;
    vector<int>curr_cost_v;
    int result_cost = INT_MAX; //最短花费时间
    bool is_find = false; //是否到达终点
    unordered_map<string, int>wait_map;
    vector<vector<int>>DirectionGrid = {{1,0},{0,1}};
};

int main()
{
    //[[0,1,0],[0,2,1],[0,0,0]]  
    //[[1,1,3]]
    string grid_str;
    getline(cin, grid_str);
    
    string wait_str;
    getline(cin, wait_str);

    Solution01 solu(grid_str, wait_str);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
